<!--
 * @Author: zengwj
 * @Date: 2021-09-18 11:14:50
 * @LastEditors: zengwj
 * @LastEditTime: 2021-09-22 14:34:36
 * @Description: 
-->
<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      /**
       * @param {string} digits
       * @return {string[]}
       */
      //        输入：digits = "23"
      // 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

      var letterCombinations = function (digits) {
        const map = [
          '',
          '',
          'abc',
          'def',
          'ghi',
          'jkl',
          'mno',
          'pqrs',
          'tuv',
          'wxyz',
        ];
        let len = digits.length;
        if (len === 0) {
          return [];
        }
        if (len === 1) {
          return map[digits].split('');
        }
        const result = [];
        const path = [];
        backtrack(digits, len, 0);
        return result;
        // 回溯算法
        function backtrack(digits, len, i) {
          if (path.length === len) {
            result.push(path.join(''));
            return;
          }
          for (const item of map[digits[i]]) {
            path.push(item);
            backtrack(digits, len, i + 1);
            path.pop();
          }
        }
      };
      console.log(letterCombinations('237'));
    </script>
  </body>
</html>
